import java.util.*;

public class Solution {
    private static final int MOD = 1000000007;

    public int InversePairs(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int[] temp = new int[nums.length];
        return mergeSort(nums, 0, nums.length - 1, temp) % MOD;
    }

    private int mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid, temp) + mergeSort(nums, mid + 1, right, temp);
        count %= MOD; // 在每次递归返回前取模，防止整数溢出
        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                count += mid - i + 1;
                count %= MOD; // 在每次更新逆序对数量后取模
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= right) {
            temp[k++] = nums[j++];
        }
        System.arraycopy(temp, left, nums, left, right - left + 1);
        return count;
    }
}
